package sort;

/**
 *  StraightInsertSort
 *  直接插入排序: 从下标为1开始，将该元素插入到前面有序序列里，越有序效率越高
 *  最好时间复杂度：O(n)
 *  时间复杂度： O(n^2)
 *  空间复杂度：O(1)
 *  稳定性：稳定
 *  数据敏感性： 敏感，越有序效率越高
 *
 *  实现：从index=1开始往前插入，先保存index=1的副本，
 */
public class StraightInsertSort {

    public static void asc(int[] a){
        int n = a.length;
        for (int i = 1; i < n; i++){
            int j = i - 1;
            int x = a[i];
            while( j >= 0 && x < a[j]){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;
        }
    }

    public static void main(String[] args) {
        int arr[] = {3,5,1,10,6};
         asc(arr);
        for (int i : arr) {
            System.out.printf("%d ", i);
        }
    }
}


